Shannon's Theorem(샤논의 정리)

원하는 특성을 가진 문체가 존재하는 지에 대해 확률로 증명하는 이론.

"모든 물체에 어떠한 점수가 있다고 하면, 평균 이상의 점수를 가진 물체가 적어도 한 개가 있을 것이다."가 그 이론의 내용이다.

존재하는 사건 A에 대해서, $P (A) > 0$ 이라면 해당 물체가 존재한다고 할 수 있다. 정확히 확률을 계산할 필요 없이, 0보다 크다는 boundary만 보이면 된다.

Example

이 때 적어도, 3명 이상의 회원이 겹치는 위원회가 존재한다.(좋은 특성)

다른 위원회 두 개에 함께 소속된 사람 3명이 존재한다는 것과 동일하다.

임의의 두 위원회를 골랐을 때, 겹치는 사람 수의 평균이 3명보다 많은 걸 보이면 된다.

E [겹치는 회원 수] = 100 \times \frac{속한 위원회 3 개 중 고른 임의의 위원회 2 개가 일치할 경우}{위원회 중 2 개를 고르는 경우} = 100 \cdot \frac{( 2 3 )}{( 2 15 )} = \frac{20}{7}

$\frac{( 2 3 )}{( 2 15 )}$ 은, 첫 번째 사람이 임의의 두 위원회에 모두 속할 확률이다. 그리고 이러한 확률은 모든 사람이 첫번째로 고르는 경우에 대해서는 동일하고, 기대값의 선형성에 의해 모두 더하기 위해 100을 곱해준다.

초기하분포의 평균을 계산하는 것과 비슷하다. 비독립적이지만, 기대값의 선형성에 의해 계산될 수 있다.